#include <stdio.h>
/*
折半插入排序
*/
void binaryInsertionSortWithSentinel(int arr[], int n) {
    // 创建一个新数组以放置哨兵
    int arrWithSentinel[n + 1];
    for (int i = 0; i < n; i++) {
        arrWithSentinel[i] = arr[i];
    }
    
    // 将哨兵（最大值）放在最后
    arrWithSentinel[n] = __INT_MAX__; // 使用整数的最大值作为哨兵

    for (int i = 1; i < n; i++) {
        int current = arrWithSentinel[i];
        int left = 0;
        int right = i; // 当前已排序部分的右边界

        // 使用折半查找找到插入位置
        while (left < right) {
            int mid = (left + right) / 2;
            if (arrWithSentinel[mid] < current) {
                left = mid + 1; // 插入位置在右侧
            } else {
                right = mid; // 插入位置在左侧
            }
        }

        // 移动元素，插入当前元素
        for (int j = i; j > left; j--) {
            arrWithSentinel[j] = arrWithSentinel[j - 1];
        }
        arrWithSentinel[left] = current; // 插入元素
    }

    // 将结果复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = arrWithSentinel[i];
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array:\n");
    printArray(arr, n);

    binaryInsertionSortWithSentinel(arr, n);

    printf("Sorted array:\n");
    printArray(arr, n);

    return 0;
}
